package SHA1;

import org.apache.commons.codec.DecoderException;
import org.apache.commons.codec.binary.Hex;

import java.math.BigInteger;
import java.nio.charset.StandardCharsets;

public class SHA1 {

    private static final byte[][] K;
    // 4字节==1个字，1个字最大的值
    private static final BigInteger UPBOUND = new BigInteger("100000000", 16);

    // 运算过程中会变，所以不能设置成静态的
    private BigInteger HA = new BigInteger("67452301", 16);
    private BigInteger HB = new BigInteger("EFCDAB89", 16);
    private BigInteger HC = new BigInteger("98BADCFE", 16);
    private BigInteger HD = new BigInteger("10325476", 16);
    private BigInteger HE = new BigInteger("C3D2E1F0", 16);

    static {
        try {
            K = new byte[][]{
                    Hex.decodeHex("5A827999"),
                    Hex.decodeHex("6ED9EBA1"),
                    Hex.decodeHex("8F1BBCDC"),
                    Hex.decodeHex("CA62C1D6")
            };
        } catch (DecoderException e) {
            throw new RuntimeException(e);
        }
    }

    /**
     * 摘要生成函数
     *
     * @param plaintext 输入的明文字符串
     * @return 输出的哈希值
     */
    public String Hash(String plaintext) {
        // 进行填充
        byte[] EM = pad(plaintext);
        // System.out.println(new BigInteger(EM).toString(2));
        // 按照 512bit / 64byte / 16个字word 进行分组
        byte[] packet = new byte[64];
        byte[] W = new byte[0];
        for (int i = 0; i < EM.length / 64; i++) {
            System.arraycopy(EM, 64 * i, packet, 0, 64);
            W = extend(packet);
            round(W);
        }

        byte[] res = new byte[20];
        System.arraycopy(BigIntToByte(HA), 0, res, 0, 4);
        System.arraycopy(BigIntToByte(HB), 0, res, 4, 4);
        System.arraycopy(BigIntToByte(HC), 0, res, 8, 4);
        System.arraycopy(BigIntToByte(HD), 0, res, 12, 4);
        System.arraycopy(BigIntToByte(HE), 0, res, 16, 4);
        StringBuilder sb = new StringBuilder(new BigInteger(res).mod(BigInteger.valueOf(2L).pow(160)).toString(16));
        // 保证输出的是160 bit
        while (sb.length() < 40) {
            sb.insert(0, '0');
        }
        return sb.substring(0);
    }

    /**
     * 消息填充函数
     *
     * @param plaintext 原始的消息
     * @return 填充后的消息的字节流，比特位数是512的整数倍，其中最后64比特是长度
     */
    private byte[] pad(String plaintext) {
        // 转化为ASCII码，将消息转换为 2 进制格式的 byteText
        byte[] byteText = plaintext.getBytes(StandardCharsets.US_ASCII);
        byte[] res;

        int padding10Bytes = -1;
        // 如果不同余于448，那么意味着需要填充100...000
        if (byteText.length * 8 % 512 != 448) {
            // 需要填充1000...000
            int residueBitNums = byteText.length * 8 % 512;
            if (residueBitNums > 448) {
                // 如果剩余的比特位数超过了448，那么需要填充到下一个分组
                padding10Bytes = ((448 - residueBitNums) + 512) / 8;
            } else {
                // 剩余的比特位数 < 448，只需要填充到448即可
                padding10Bytes = (448 - residueBitNums) / 8;
            }
        } else {
            padding10Bytes = 0;
        }
        // 原本的长度 + 填充100...00所需要字节数 + 填充长度（64比特）所需的字节数
        res = new byte[byteText.length + padding10Bytes + 64 / 8];
        // 填充原本的字节
        System.arraycopy(byteText, 0, res, 0, byteText.length);
        // 填充100...00
        res[byteText.length] = (byte) 0x80;
        for (int i = 1; i < padding10Bytes; i++) {
            res[byteText.length + i] = (byte) 0x00;
        }
        // 填充长度
        BigInteger realBitsLen = BigInteger.valueOf(byteText.length).multiply(BigInteger.valueOf(8L));
        BigInteger maxBitLen = BigInteger.valueOf(2L).pow(64);
        if (realBitsLen.compareTo(maxBitLen) >= 0) {
            // 原始长度不能超过2^64次方，否则报错
            throw new RuntimeException("原始长度不能超过2^64次方!");
        }
        // 加上2^64次方是为了转换成字节数组时，字节数组的长度等于9，从第二个字节开始
        byte[] lenArray = realBitsLen.add(maxBitLen).toByteArray();
        for (int i = 0; i < 8; i++) {
            res[byteText.length + padding10Bytes + i] = lenArray[i + 1];
        }
        return res;
    }

    /**
     * 字扩展函数
     *
     * @param M 输入16个字（也就是64个字节）
     * @return 输出经过扩展的字节W，扩展后为80个字（也就是320个字节）
     */
    private byte[] extend(byte[] M) {
        if (M == null || M.length != 64) {
            // 检查 M 的输入是否正常，如果指针为null或者字节个数少于64个，则报错
            throw new RuntimeException("输入的分组的字节数不为64！");
        }
        byte[] W = new byte[4 * 80];
        System.arraycopy(M, 0, W, 0, 64);
        byte[] tempBytes = new byte[4];
        for (int i = 16; i < 80; i++) {
            // W[j] = W[j-3] xor W[j-8] xor W[j-14] xor W[j-16]
            tempBytes[0] = (byte) (W[(i - 3) * 4] ^ W[(i - 8) * 4] ^ W[(i - 14) * 4] ^ W[(i - 16) * 4]);
            tempBytes[1] = (byte) (W[(i - 3) * 4 + 1] ^ W[(i - 8) * 4 + 1] ^ W[(i - 14) * 4 + 1] ^ W[(i - 16) * 4 + 1]);
            tempBytes[2] = (byte) (W[(i - 3) * 4 + 2] ^ W[(i - 8) * 4 + 2] ^ W[(i - 14) * 4 + 2] ^ W[(i - 16) * 4 + 2]);
            tempBytes[3] = (byte) (W[(i - 3) * 4 + 3] ^ W[(i - 8) * 4 + 3] ^ W[(i - 14) * 4 + 3] ^ W[(i - 16) * 4 + 3]);
            // W[j] <<< 1，整个字循环左移 1 bit
            BigInteger tempWord = new BigInteger(tempBytes).mod(UPBOUND);
            tempWord = reShiftLeft(tempWord, 1);
            // 求模数后再加一个2^32次方，保证求字节数组后字节个数为5个，舍弃第1个
            tempWord = tempWord.mod(UPBOUND).add(UPBOUND);
            // System.out.println(beautiful(tempWord.toString(2).substring(1)));
            byte[] byteArray = tempWord.toByteArray();
            System.arraycopy(byteArray, 1, W, i * 4, 4);
        }
        return W;
    }

    /**
     * 轮函数round，进行多轮迭代
     *
     * @param W 输入的是经过扩展的字节W，一共320个字节
     */
    private void round(byte[] W) {
        if (W == null || W.length != 320) {
            // 检查 W 的输入是否正常，如果指针为null或者字节个数少于320个，则报错
            throw new RuntimeException("输入的分组扩展后的字节数不为320！");
        }
        // 处理的单元是 字，1个字==4字节，一共是320字节，一共需要80轮
        BigInteger A = new BigInteger(String.valueOf(HA));
        BigInteger B = new BigInteger(String.valueOf(HB));
        BigInteger C = new BigInteger(String.valueOf(HC));
        BigInteger D = new BigInteger(String.valueOf(HD));
        BigInteger E = new BigInteger(String.valueOf(HE));

        for (int i = 0; i < 80; i++) {
            BigInteger Wj = new BigInteger(new byte[]{W[i * 4], W[i * 4 + 1], W[i * 4 + 2], W[i * 4 + 3]});
            BigInteger temp = reShiftLeft(A, 5)
                    .add(new BigInteger(f(B, C, D, i / 20)))
                    .add(E).add(Wj).add(new BigInteger(K[i / 20]));
            E = D.mod(UPBOUND);
            D = C.mod(UPBOUND);
            C = reShiftLeft(B, 30).mod(UPBOUND);
            B = A.mod(UPBOUND);
            A = temp.mod(UPBOUND);
        }

        HA = HA.add(A).mod(UPBOUND);
        HB = HB.add(B).mod(UPBOUND);
        HC = HC.add(C).mod(UPBOUND);
        HD = HD.add(D).mod(UPBOUND);
        HE = HE.add(E).mod(UPBOUND);

    }

    /**
     * 逻辑函数 f
     *
     * @param B    逻辑函数输入之一
     * @param C    逻辑函数输入之二
     * @param D    逻辑函数输入之三
     * @param step 不同步对应的不同的轮次
     * @return 返回逻辑函数运行结果
     */
    private byte[] f(BigInteger B, BigInteger C, BigInteger D, int step) {

        byte[] b = BigIntToByte(B);
        byte[] c = BigIntToByte(C);
        byte[] d = BigIntToByte(D);
        int len = b.length;
        // 返回的结果
        byte[] res = new byte[len];
        for (int i = 0; i < len; i++) {
            if (step == 0) {
                res[i] = (byte) ((b[i] & c[i]) | ((~b[i]) & d[i]));
            } else if (step == 1 || step == 3) {
                res[i] = (byte) (b[i] ^ c[i] ^ d[i]);
            } else if (step == 2) {
                res[i] = (byte) ((b[i] & c[i]) | (b[i] & d[i]) | (c[i] & d[i]));
            }
        }
        return res;
    }

    private static byte[] BigIntToByte(BigInteger target) {
        // 去掉超过上限的，和保证字节数组一共有5个元素
        target = target.mod(UPBOUND).add(UPBOUND);
        byte[] tbytes = target.toByteArray();
        return new byte[]{tbytes[1], tbytes[2], tbytes[3], tbytes[4]};
    }

    private static BigInteger reShiftLeft(BigInteger target, int shiftNum) {
        // 统一按照32比特来处理
        BigInteger left = target.shiftLeft(shiftNum).mod(UPBOUND);
        BigInteger right = target.shiftRight(32 - shiftNum).mod(UPBOUND);
        return left.add(right);
    }

    private String beautiful(String input) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < input.length(); i++) {
            sb.append(input.charAt(i));
            if ((i + 1) % 8 == 0) {
                sb.append(',');
            }
        }
        return sb.substring(0);
    }
}
